Vấn đề này lần đầu tiên được đề cập vào năm 1852 bởi Francis Guthrie khi ông thử tô màu bản đồ nước Anh và ông nhận ra rằng chỉ cần bốn màu khác nhau là đủ. Ông đã đem vấn đề này hỏi người anh trai là Fredrick, lúc đó đang là sinh viên của trường Đại học Học viện London (UCL). Fredrick đã đưa vấn đề này hỏi thầy của mình là nhà toán học Augustus De Morgan nhưng người thầy cũng chưa biết rõ vấn đề này.

Người đầu tiên giới thiệu vấn đề ra trước công chúng là nhà toán học Arthur Cayley vào năm 1878 tại Hội Toán học London, ông đã chỉ ra người đề cập vấn đề là De Morgan. Vào tháng 10/1852, giáo sư De Morgan ở trường Đại học Luân Đôn viết thư cho đồng nghiệp của mình là ông William Hamilton để bàn về bài toán: "Mọi bản đồ đều có thể tô bằng 4 màu sao cho hai nước nằm kề nhau phải được tô bằng hai màu khác nhau".[1]

Người đầu tiên chứng minh định lý này là Alfred Kempe vào năm 1879. Năm 1880, có thêm một cách chứng minh khác của Peter Guthrie Tait. Nhưng đến năm 1890 Percy Heawood đã chỉ ra sai lầm trong cách chứng minh của Kempe, và đến năm 1891 Julius Petersen chỉ ra sai lầm trong cách chứng minh của Tait.

Trong việc chỉ ra sai lầm của Kempe, Heawood còn chứng minh rằng tất cả các Đồ thị phẳng phải sử dụng năm màu khác nhau, và làm cơ sở phát triển cho lời giải sau này. Xem Định lý năm màu.

Trong những năm 1960 và 1970, nhà toán học người Đức là Heinrich Heesch đã phát triển phương pháp sử dụng máy vi tính cho việc chứng minh vấn đề.

Năm 1976, cuối cùng thì định lý cũng được chứng minh bởi Kenneth Appel và Wolfgang Haken tại trường Đại học Illinois với sự trợ giúp của máy vi tính (trong khoảng 1000 giờ máy). Nhà khoa học John A. Koch cũng góp phần cải tiến thuật toán để giải quyết trọn vẹn bài toán 4 màu.[2]